package ru.usu.gv.utils.imports.dynamic;

import ru.usu.gv.utils.CommonUtilities;
import ru.usu.gv.utils.Pair;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * @author spupyrev
 * 02.03.2010
 */
public class Cliques
{
	private static int PERIOD = 7;
	private static int COUNT = 21;

	private static int CL_SIZE = 4;

	private static class Clique implements Comparable<Clique>
	{
		List<Integer> list = new ArrayList<Integer>();

		public Clique()
		{
		}

		public void add(int element)
		{
			list.add(element);
		}

		public boolean canAdd(int element, Map<Integer, Map<Integer, Double>> edges)
		{
			if (list.contains(element))
				return false;

			for (Integer i : list)
				if (!edges.get(i).containsKey(element))
					return false;
			return true;
		}

		@Override
		public int hashCode()
		{
			final int prime = 31;
			int result = 1;
			result = prime * result + ((list == null) ? 0 : list.hashCode());
			return result;
		}

		@Override
		public boolean equals(Object obj)
		{
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			Clique other = (Clique) obj;
			if (list == null)
			{
				if (other.list != null)
					return false;
			}
			else if (!list.equals(other.list))
				return false;
			return true;
		}

		@Override
		public String toString()
		{
			String s = "";
			for (Integer i : list)
				s += i + " ";
			//s += "\n";
			return s;
		}

		public int getSize()
		{
			return list.size();
		}

		public int compareTo(Clique o)
		{
			return Integer.valueOf(list.hashCode()).compareTo(Integer.valueOf(o.list.hashCode()));
		}
	}

	public static void main(String argc[])
	{
		VNCData data = new VNCData();
		List<Set<Clique>> cliques = new ArrayList();
		for (int i = 0; i < COUNT; i++)
		{
			Map<Integer, Map<Integer, Double>> edges = data.getEdges(PERIOD * i, PERIOD * (i + 1), 1);
			Set<Clique> cl = findCliques(edges);

			Clique testClique = new Clique();
			testClique.add(31);
			testClique.add(4);
			testClique.add(25);
			testClique.add(151);

			if (cl.contains(testClique))
				System.out.println(i);

			cliques.add(cl);
		}

		findLargest(cliques);
	}

	private static void findLargest(List<Set<Clique>> cliques)
	{
		Map<Clique, Integer> cnt = new HashMap();
		for (Set<Clique> cl : cliques)
			for (Clique c : cl)
				CommonUtilities.incrementMap(cnt, c, 1);

		List<Pair<Integer, Clique>> pairs = new ArrayList();
		for (Clique cl : cnt.keySet())
		{
			pairs.add(new Pair(cnt.get(cl), cl));
		}
		Collections.sort(pairs);
		for (int i = pairs.size() - 1; i >= 0; i--)
			System.out.println(pairs.get(i).getFirst() + "  --  " + pairs.get(i).getSecond());
	}

	private static Set<Clique> findCliques(Map<Integer, Map<Integer, Double>> edges)
	{
		Set<Clique> res = new HashSet();
		for (int i : edges.keySet())
		{
			Clique c = new Clique();
			c.add(i);
			findCliques(edges, c);
			if (c.getSize() >= CL_SIZE)
				res.add(c);
		}
		return res;
	}

	private static void findCliques(Map<Integer, Map<Integer, Double>> edges, Clique c)
	{
		for (int i : edges.keySet())
			if (c.canAdd(i, edges))
			{
				c.add(i);
				findCliques(edges, c);
			}
	}

}
